import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-04-12
 * Time: 16:04
 */
public class Heap {
    public int[] elem;//
    public int curSize;

    public Heap() {
        this.elem = new int[10];
    }

    /**
     * 初始化数组
     *
     * @param arr
     */
    public void init(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            curSize++;
        }
    }


    /**
     * 创建大根堆
     */
    public void createHeap() {
        for (int parent = (curSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, curSize);
        }
    }

    //交换两个数
    public void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //从下往上调整
    public void shiftDown(int parent, int end) {
        int child = 2 * parent + 1;
        while (child < end) {
            if (child + 1 < end && elem[child] < elem[child + 1]) {
                child++;
            }
            //保证child是孩子中最大的值
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    //在堆中添加一个元素,并且添加后的堆也是大根堆
    public void offer(int val) {
        isFull();
        elem[curSize] = val;
        curSize++;
        int child = curSize - 1;
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    //出堆顶元素
    /*
    public int poll() {
    }*/


    public void show() {
        for (int i = 0; i < curSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

    //容量是否满
    public void isFull() {
        if (elem.length == curSize) {
            this.elem = Arrays.copyOf(elem, elem.length * 2);
        }

    }

    //是否为空
    public boolean isEmpty() {
        return curSize == 0;
    }

}
